#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <sstream>

char path[256];
int gSum;
int tSum;
std::string ratio(int now, int original);
void showTree(class element *root,int depth);
void dumpTree(class element *root);

class element {
public:
    int value;
    int appearences;
    class element *left;
    class element *right;

    element() { left=right=NULL; }
};
int caseInsensitiveLessThan(const void *s1, const void *s2);


int caseInsensitiveLessThan(const void *s1, const void *s2)
{
    return ((element *)s1)->appearences < ((element *)s2)->appearences;
}

int main(int argc, char **argv)
{


    //cout << "Hello World!" << endl;
    if (argc!=2) {
        std::cerr << "Usage: "<< argv[0]<< " filename" << std::endl;
        return 5;
    }
    std::ifstream::pos_type size;
    unsigned char * memblock;
    std::ifstream file (argv[1], std::ios::in|std::ios::binary|std::ios::ate);
      if (file.is_open())
      {
        size = file.tellg();
        memblock = new unsigned char [size];
        file.seekg (0, std::ios::beg);
        file.read ((char *)memblock, size);
        file.close();

        std::cout << "Loaded " << size << " bytes in memory..."<<std::endl;
        element freq[256];
        for(int i=0; i<256; ++i) {
            freq[i].appearences=0;
            freq[i].value=i;
        }

        for(int i=0; i<size; ++i) {
            ++freq[(unsigned int) memblock[i]].appearences;
            //std::cout << (unsigned int) memblock[i] << " ";
        }
        qsort(freq,256,sizeof(element),caseInsensitiveLessThan);


        int c=0;
        int sum=0;
        for(int i=0; i<256; ++i){
            if (freq[i].appearences) {
                char ch=freq[i].value;
                std::cout << ++c << "(" << ch << ") - " << freq[i].value << ", "<< freq[i].appearences<< " appearences."<< std::endl;
                sum+= freq[i].appearences*c+8;
            }
        }
        std::cout << "Silly compression size: " << sum/8 << std::endl
                  << "c: " << c <<std::endl;

        //hmm, can't handle cases where c==1 FIXME
        while (c>1) {
            class element *left = new element();
            class element *right = new element();
            if (freq[c-1].appearences>freq[c-2].appearences) {
                *left= freq[c-1];
                *right=freq[c-2];
            } else {
                *left= freq[c-2];
                *right=freq[c-1];
            }
            freq[c-2].appearences=left->appearences+right->appearences;
            freq[c-2].left=left;
            freq[c-2].right=right;
            --c;
            //overkill, a binary insertion should be made here
            qsort(freq,c,sizeof(element),caseInsensitiveLessThan);
        }
        gSum=0;
        tSum=0;
        showTree(&freq[0],0);

        std::cout << "Compressed size: " << (int) (gSum/8.0) << "/" << size  << " (" << ratio(gSum/8.0,size) << "%)"
                  << " Huffman tree isn't dumped and so not included in compression (i.e. compression will be slightly worse)"<< std::endl;

        std::cout << "Compressed size: " << (int) ((tSum+gSum)/8.0) << "/" << size  << " (" << ratio((tSum+gSum)/8.0,size) << "%)" << std::endl;
        //dumpTree(&freq[0]);
        std::cout << "tree size: " << tSum/8.0 << std::endl;
        delete[] memblock;
      }
      else std::cerr << "Unable to open file";
    return 0;
}

#include <iomanip>
std::string ratio(int now, int original)
{
    std::ostringstream ss;

    ss << std::setprecision(4) << now*100.0/original;

    return ss.str();
}

#include <assert.h>

void showTree(class element *root,int depth)
{
//    std::cout << "Depth: "<< depth << std::endl;
//    for(int i=0; i<depth; ++i) std::cout << path[i];
//    std::cout << std::endl;


    if (root->left==NULL && root->right==NULL) {
        std::cout << root->value << " (" << (char) root->value << ") - ";
        for(int i=0; i<depth; ++i) std::cout << path[i];
        gSum+=depth*root->appearences;
        std::cout << " " <<depth*root->appearences << "/" << 8*root->appearences<< " bits. (" << ratio(depth*root->appearences,8*root->appearences) << "%)"<< std::endl;

        tSum+=8+4+depth;
        return;
    }
    assert(root->left!=NULL);
    assert(root->right!=NULL);
    path[depth]='0';
    showTree(root->left,depth+1);
    path[depth]='1';
    showTree(root->right,depth+1);
}

void dumpTree(class element *root)
{
    if (root->left && root->right) {
        //std::cout << "0" << std::endl;

        if (!((root->left->right==NULL && root->left->left==NULL)
             ||(root->right->right==NULL && root->right->left==NULL))) {
            std::cout << "00" <<std::endl;
            dumpTree(root->left);
            dumpTree(root->right);
            return;
        }
        if ((root->left->right==NULL && root->left->left==NULL)
           && (root->right->right==NULL && root->right->left==NULL)
                ) {
            std::cout << "1" << (char)root->left->value << "1" << (char)root->right->value<< std::endl;
            return;
        }
        if ((root->left->right==NULL && root->left->left==NULL)) {
            std::cout << "1" << (char)root->left->value << "0" << std::endl;
            dumpTree(root->right);
        }
        if ((root->right->right==NULL && root->right->left==NULL)) {
            std::cout << "01" << (char)root->right->value << std::endl;
            dumpTree(root->left);
        }

    } else {
        std::cout << "*****" << (char)root->value << " ";
    }
}

/*
  0
  01A
  1B0
  1D1C


  */
